package algorithm.graph;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Path {

    private Graph graph;

    private boolean visited[];

    private int[] from;


    public Path(Graph graph, int s) {
        this.graph = graph;
        this.visited = new boolean[graph.V()];
        this.from = new int[graph.V()];
        for (int i = 0; i < graph.V(); i++) {
            visited[i] = false;
            from[i] = -1;
        }
        //寻路
        dfs(s);

    }

    private void dfs(int v) {
        visited[v] = true;

        Iterator<Integer> iterator = graph.iterator(v);
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            if (!visited[value]) {
                from[value] = v;
                dfs(value);
            }
        }
    }


    boolean hasPath(int w) {
        return visited[w];
    }

    List<Integer> path(int w) {
        LinkedList<Integer> list = new LinkedList<>();
        int p = w;
        while (p != -1) {
            list.addFirst(p);
            p = from[p];
        }
        return list;
    }


    void showPath(int w) {
        List<Integer> path = path(w);
        for (Integer integer : path) {
            System.out.print(integer);
            System.out.print("->");
        }
    }


    public static void main(String[] args) {
        String filename = "testG.txt";
        Graph g = ReadGraph.readGraph(SparseGraph.class, filename);
        g.show();
        System.out.println();

        Path path = new Path(g, 0);
        System.out.println("Path from 0 to 6 : ");
        path.showPath(6);

        System.out.println("==========================================Over");
    }
}
